package com.shan.ai.combo;

import java.io.File;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.UUID;

import com.shan.ai.combo.IComboConstant.BeadList;
import com.shan.ai.combo.IComboConstant.BeadType;
import com.shan.ai.combo.IComboConstant.Point;
import com.shan.ai.combo.impl.ScreenParser;

public abstract class BaseCombo implements ICombo, IComboConstant {

    public long count = 0;

    /**
     * 终止标识
     */
    protected boolean bFinalStop;

    /**
     * 局面唯一标识
     */
    public static String uuid;

    //当前最大局面值
    protected double maxCost;

    //当前记录走过的路径
    protected List<Point> stepList;
    protected List<Point> maxStepList;

    // // 当前Combo链表
    // public List<BeadList> comboList;
    protected List<BeadList> maxcomboList;

    // 原始局面
    protected BeadType[][] initBeads;

    // 临时局面
    protected BeadType[][] runTimeBeads;

    protected BeadType[][] maxBeads;

    protected long startTime;

    public BaseCombo() {
        // cost = -1;
        uuid = UUID.randomUUID().toString().substring(0, 4);

        stepList = new ArrayList<IComboConstant.Point>();
        initBeads = initBoard();

        maxBeads = new BeadType[MAX_ROW][MAX_COLUMN];
        // comboList = new ArrayList<BeadList>();
        startTime = -1;
        bFinalStop = false;

    }

//    public static void main(String[] args) {
//
//        BaseCombo board = new BaseCombo();
//
//        long t1 = System.currentTimeMillis();
//
//        // board.genRandomBoard();
//        board.printBorad(board.initBeads);
//
//        board.move(board.initBeads);
//
//        // board.printList();
//
//        board.printBorad(board.maxBeads);
//        // board.computeCombo(board.maxBeads);
//
//        long t2 = System.currentTimeMillis();
//
//        System.out.println("Time(s):" + (t2 - t1));
//        // System.out.println("Combo:" + board.comboList.size());
//        System.out.println("Move:" + board.count);
//        System.out.println("Cost(s):" + board.maxCost);
//
//        for (int i = 0; i < board.maxStepList.size(); i++) {
//            System.out.print(board.maxStepList.get(i) + "->");
//        }
//
//        System.out.println();
//
//        for (BeadList combo : board.maxcomboList) {
//            for (int i = 0; i < combo.size(); i++) {
//                System.out.print(combo.get(i) + "->");
//            }
//            System.out.println();
//        }
//
//        ScreenCapUtils.drawLines(board.maxStepList, uuid + "_" + String.valueOf(board.maxCost));
//
//    }

    /**
     * 计算当前combo，核心算法
     * currBoard:需要计算的局面
     * afterBoard：计算结果局面
     */
    public List<BeadList> computeCombo(BeadType[][] currBoard) {

        boolean bRemove = false;

        List<BeadList> comboList = new ArrayList<BeadList>();

        // 创建临时变量，用于计算Combo
        BeadType[][] beads = copyBoard(currBoard);

        BeadList tmpList = new BeadList();
        do {
            bRemove = false;

            
            // 检查某点是否可以加入
            for (int i = 0; i < MAX_ROW; i++) {
                for (int j = 0; j < MAX_COLUMN; j++) {
                    BeadList newList = checkOnePoint(i, j, beads, comboList);
                    if (newList!=null && newList.size()>0) {
                        bRemove = true;
                        tmpList.addAll(newList);
                    }
                }
            }

            if (!bRemove) {
                break;
            }

            // 存在消除，则移除已消除的：链表中的置空
            for (Point point : tmpList) {
                beads[point.x][point.y] = BeadType.none;
            }
            
            tmpList.clear();
            
            // 其它下移
            for (int i = 1; i < MAX_ROW; i++) {
                for (int j = 0; j < MAX_COLUMN; j++) {
                    if (beads[i][j] == BeadType.none) {
                        for (int i2 = i; i2 > 0; i2--) {
                            beads[i2][j] = beads[i2 - 1][j];
                        }
                        beads[0][j] = BeadType.none;
                    }
                }
            }
        } while (bRemove);

        return comboList;
    }

    /**
     * 基于某点计算Combo
     * 
     * @param i
     * @param j
     * @return 是否存在Combo
     */
    private BeadList checkOnePoint(int i, int j, BeadType[][] beads, List<BeadList> comboList) {

        if (beads[i][j] == BeadType.none ) {
            return null;
        }

        BeadList newlist = new BeadList();

        newlist.addAllOnce(addIfSame(i, j, 0, beads));
        newlist.addAllOnce(addIfSame(i, j, 1, beads));

        if (newlist.size() > 0) {
            newlist.type = beads[i][j];
            addOrMergeList(newlist, beads, comboList);
        }

        return newlist;
    }

    /**
     * 加入某个链表或者是一个新的Combo
     * 
     * @param newlist
     */
    public void addOrMergeList(BeadList newlist, BeadType[][] beads, List<BeadList> comboList) {
        boolean isExist = false;
        int comboSize = comboList.size();
        int index = -1;
        BeadType newType = newlist.type;

    
        for (int i = 0; i < comboSize; i++) {
            BeadList list = comboList.get(i);

            BeadType type = list.type;

            for (Point point : list) {
                if (newType.equals(type)) {
                    if (newlist.contains(point)) {
                        isExist = true;
                        index = i;
                        break;
                    } else {
                        for (Point point2 : newlist) {
                            if (Math.abs(point.x - point2.x) + Math.abs(point.y - point2.y) <= 1) {
                                isExist = true;
                                index = i;
                                break;
                            }
                        }
                    }

                }

            }

            if (isExist) {
                break;
            }
        }

        if (isExist) {
            // 可能存在当newList同时被两个Combo包含时，需要合并这两个Combo
            BeadList sameList = comboList.remove(index);
            sameList.addAllOnce(newlist);
            addOrMergeList(sameList, beads, comboList);

        } else {
            comboList.add(newlist);
        }

    }

    /**
     * 
     * 返回可以组成3个的链表
     * 
     * @param list
     * @param i
     * @param j
     * @param direct
     */
    private BeadList addIfSame(int i, int j, int direct, BeadType[][] beads) {
        BeadList list = new BeadList();
        switch (direct) {
        case 0:
            if (j > 0 && j < MAX_COLUMN - 1) {
                if (beads[i][j].equals(beads[i][j + 1]) && beads[i][j].equals(beads[i][j - 1])) {
                    list.add(new Point(i, j));
                    list.add(new Point(i, j + 1));
                    list.add(new Point(i, j - 1));
                }
            }
        case 1:
            if (i > 0 && i < MAX_ROW - 1) {
                if (beads[i][j].equals(beads[i + 1][j]) && beads[i][j].equals(beads[i - 1][j])) {
                    list.add(new Point(i, j));
                    list.add(new Point(i + 1, j));
                    list.add(new Point(i - 1, j));
                }
            }

        default:
            break;
        }

        return list;
    }

    /**
     * 打印步骤
     */
    public void printList() {
        for (int i = 0; i < stepList.size(); i++) {
            System.out.print(stepList.get(i) + "->");
        }
        System.out.print(maxCost);
        System.out.println();

    }

    public void printList(List list) {
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i) + "->");
        }

        System.out.println();

    }

    /**
     * 随机生成局面
     */
    public void genRandomBoard() {
        Random r = new Random();
        for (int i = 0; i < MAX_ROW; i++) {
            for (int j = 0; j < MAX_COLUMN; j++) {
                runTimeBeads[i][j] = BeadType.values()[r.nextInt(6)];
            }
        }

    }

    // public void getBoard() {
    // tmpBeads = new BeadType[][] { { BeadType.fire, BeadType.water,
    // BeadType.fire, BeadType.dark, BeadType.fire, BeadType.heart },
    // { BeadType.dark, BeadType.water, BeadType.light, BeadType.fire,
    // BeadType.light, BeadType.water },
    // { BeadType.water, BeadType.fire, BeadType.light, BeadType.light,
    // BeadType.fire, BeadType.heart },
    // { BeadType.fire, BeadType.dark, BeadType.water, BeadType.heart,
    // BeadType.heart, BeadType.fire },
    // { BeadType.wood, BeadType.dark, BeadType.heart, BeadType.light,
    // BeadType.dark, BeadType.heart } };
    //
    // }

    /**
     * 打印局面
     */
    public void printBorad(BeadType[][] beads) {
        // System.out.println("Board:");
        for (int i = 0; i < MAX_ROW; i++) {
            for (int j = 0; j < MAX_COLUMN; j++) {
                System.out.print(String.format("%10s", beads[i][j] + "(" + i + "," + j + ")") + " ");
                // System.out.print(String.format("%10s", beads[i][j].ordinal()
                // + "(" + i + "," + j + ")") + " ");
            }
            System.out.println();
        }
    }

    /**
     * 移动并计算局面值
     * 
     * @param from
     * @param to
     */
    public double moveAndcost(Point from, Direct direct) {

        // if(stepList.size() >= MAX_STEP){
        // cost = -1;
        // return;
        // }

        Point to = null;
        switch (direct) {
        case up:
            to = new Point(from.x - 1, from.y);
            break;
        case down:
            to = new Point(from.x + 1, from.y);
            break;
        case left:
            to = new Point(from.x, from.y - 1);
            break;
        case right:
            to = new Point(from.x, from.y + 1);
            break;

        default:
            break;
        }

        if (to.x < 0 || to.x >= MAX_ROW || to.y < 0 || to.y >= MAX_COLUMN) {
            // cost = -1;
            return -1;
        }

        if (stepList.contains(to)) {
            // cost = -1;
            return -1;
        }

        // if (from.equals(to)) {
        // // cost = -1;
        // return -1;
        // }

        count++;

        if (count % 1000000 == 0) {
            System.out.println("Move:" + count);
        }

        // recordBoard();
        stepList.add(to);

        BeadType temp = runTimeBeads[from.x][from.y];
        runTimeBeads[from.x][from.y] = runTimeBeads[to.x][to.y];
        runTimeBeads[to.x][to.y] = temp;

        // recordBoard();
        List<BeadList> comboList = computeCombo(runTimeBeads);
        double cost = computeCost(comboList);

        if (cost > maxCost || (maxStepList != null && cost == maxCost && stepList.size() < maxStepList.size())) {
            maxCost = cost;
            maxStepList = new ArrayList<IComboConstant.Point>(stepList);
            maxcomboList = new ArrayList<IComboConstant.BeadList>(comboList);
            System.out.println("Update Max Cost:" + cost + " [" + (System.currentTimeMillis() - startTime) + "] Combo:" + maxcomboList.size() + " Move:"
                    + count);
            printList();
            printBorad(runTimeBeads);
            for (BeadList combo : comboList) {
                for (int i = 0; i < combo.size(); i++) {
                    System.out.print(combo.get(i) + "->");
                }
                System.out.println();
            }

            maxBeads = copyBoard(runTimeBeads);

        }
        // resetBoard();

        // printList();
        // printBorad();
        return cost;
    }

    public void moveBack() {
        if (stepList.size() < 2) {
            // bOnceStop = true;
            return;
        }
        Point from = stepList.remove(stepList.size() - 1);
        Point to = stepList.get(stepList.size() - 1);

        BeadType temp = runTimeBeads[from.x][from.y];
        runTimeBeads[from.x][from.y] = runTimeBeads[to.x][to.y];
        runTimeBeads[to.x][to.y] = temp;
    }

    public void moveIn() {

        if (bFinalStop) {
            return;
        }

        // 终止条件满足
        if (isEndCondition()) {
            bFinalStop = true;
            return;
        }

        if (stepList.size() >= MAX_STEP) {
            // bOnceStop = true;
            moveBack();

            return;
        }

        Point currPoint = stepList.get(stepList.size() - 1);

        for (Direct direct : Direct.values()) {

            double currCost = moveAndcost(currPoint, direct);
            // printList();
            if (currCost >= 0) {
                moveIn();
                if (bFinalStop) {
                    return;
                }
                // resetBoard();
            }
        }

        moveBack();

        return;
    }

    // /**
    // * 重置局面
    // */
    // private void resetBoard() {
    // for (int i = 0; i < MAX_ROW; i++) {
    // for (int j = 0; j < MAX_COLUMN; j++) {
    // runTimeBeads[i][j] = initBeads[i][j];
    // }
    // }
    // }
    //
    // private void recordBoard() {
    // for (int i = 0; i < MAX_ROW; i++) {
    // for (int j = 0; j < MAX_COLUMN; j++) {
    // initBeads[i][j] = runTimeBeads[i][j];
    // }
    // }
    // }

    public BeadType[][] copyBoard(BeadType[][] srcBeads) {
        BeadType[][] newBoard = new BeadType[MAX_ROW][MAX_COLUMN];
        for (int i = 0; i < MAX_ROW; i++) {
            for (int j = 0; j < MAX_COLUMN; j++) {
                newBoard[i][j] = srcBeads[i][j];
            }
        }

        return newBoard;
    }

    /*
     * (non-Javadoc)
     * 
     * @see com.shan.ai.combo.ICombo#isEndCondition()
     */
    @Override
    public boolean isEndCondition() {
        if (maxCost > MAX_COST) {
            System.out.println("局面值达到");
            return true;
        }

        if (System.currentTimeMillis() - startTime > OVER_TIME) {
            System.out.println("时间达到");
            return true;
        }

        return false;
    }

    /*
     * (non-Javadoc)
     * 
     * @see com.shan.ai.combo.ICombo#move(com.shan.ai.combo.ICombo.BeadType[][])
     */
    @Override
    public List<Point> move(BeadType[][] initBeads) {
        startTime = System.currentTimeMillis();

        for (int i = 0; i < MAX_ROW; i++) {
            for (int j = 0; j < MAX_COLUMN; j++) {

                runTimeBeads = copyBoard(initBeads);

                Point startPoint = new Point(i, j);
                stepList.clear();
                stepList.add(startPoint);

                moveIn();

                // bOnceStop = false;
                // System.out.println("Once Count:[" + i + "," + j + "]" +
                // count);
                //
                // bFinalStop = true;
                if (bFinalStop) {
                    return maxStepList;
                }
            }
        }

        System.out.println("Move over");
        return maxStepList;
    }

    /*
     * (non-Javadoc)
     * 
     * @see
     * com.shan.ai.combo.ICombo#computeCost(com.shan.ai.combo.ICombo.BeadType
     * [][])
     */
    @Override
    public double computeCost(List<BeadList> comboList) {
        double cost = 0;
        //combo倍率
        double p1 = (1 + (comboList.size() - 1) * 0.25);
        int count = 0;
        
        for (BeadList beadList : comboList) {
            //3串额外多的才增加倍率，否则就是1倍
            count += beadList.size() - 3;
        }

        double p2 = comboList.size() + count * 0.25;
        cost = p1 * p2;

        return cost;
    }

    /*
     * (non-Javadoc)
     * 
     * @see com.shan.ai.combo.ICombo#initBoard()
     */
    @Override
    public BeadType[][] initBoard() {
        ScreenParser.srceenCap(ScreenParser.screenCapPath);
        return ScreenParser.parseScreenCap(new File(ScreenParser.screenCapPath));
    }

}
